1. Field of the Invention
Certain embodiments of the present invention are directed generally to methods for sharing a memory buffer in a data distribution device. Certain other embodiments of the present invention are generally directed to data distribution devices for implementing such methods.
2. Description of the Related Art
Generally, data distribution devices according to the related art, such as, for example, routers and shared memory switches, have one pool of data memory and many pointers that reference that pool. As shown in FIG. 1, a pool of data memory according to the related art may include a cell pool buffer 100. The cell pool buffer 100 typically is accessed by ports of the data distribution device that includes the buffer 100, as illustrated in FIG. 1 by the references to representative ports P0, P1 . . . P9 . . . PN, each of which are operably connected to portions of the buffer 100.
According to the related art, each port P0, P1 . . . P9 . . . PN acts as an ingress and/or egress for data packets in one or more Classes of Service (COSs). As shown in FIG. 1, the cell pool buffer 100 has regions thereof allocated to several COSs for each of the ports.
According to the buffer 100 illustrated in FIG. 1, each port has a buffer region 130, 140, 150, 160 allocated/dedicated exclusively to it. Each allocated buffer region 130, 140, 150, 160 is of a set size and includes a statically-allocated number of memory cells. Each region 130, 140, 150, 160 includes a low-water mark (LWM) 110 and a high-water mark (HWM) 120. The LWM 110 sets a minimum level of cells or buffer allocation for each of the COSs supported by a given port. The HWM 120 sets a maximum level of cell or buffer allocation for each of the ports.
Typically, when in use, a data distribution device that includes the buffer 100 illustrated in FIG. 1 makes use of the buffer 100 when some of the ports P0, P1 . . . P9 . . . PN in the device are communicating with other ports, usually on other devices in a network. For example, the buffer 100 may be used when the port P1 in FIG. 1 is exchanging data packets with one or more ports on other devices in the network to which the port P1 is operably connected.
If only two ports in a network are communicating, and if each of these ports has the same capacity/bandwidth available for exchanging data packets or, more generally, datagrams (which may include, for example, cells, bit strings, and packets), only a minimum fixed amount of the cell pool buffer 100 will typically be used. Rather, under such circumstances, packets received by the ingress port will be able to “flow through” the ingress port and will be distributed through egress ports without having to be stored in memory for an extended period of time. However, if one of the ports that is operably connected to the cell pool buffer 100 begins communicating with two or more other ports simultaneously, or if the bandwidth of a receiving (ingress) port is higher than the bandwidth of a transmitting port, a problem of over-subscription may occur at the egress port.
When an egress port is over-subscribed, more data packets, attempt to flow through the egress port than the port can handle. Hence, the packets are usually either stored in the buffer 100 or dropped/discarded. In a preferable data distribution device such as, for example, a router or switch, the over-subscription is only a temporary situation. Therefore, under preferable conditions, the cell pool buffer 100 is large enough to be capable of storing packets that cannot be immediately distributed through an egress port. Under these preferable conditions, the packets are stored until an egress port becomes available for these packets.
In other words, under preferable conditions, when an egress port in a data distribution device is over-subscribed, packets are stored temporarily in the buffer 100. Then, when the burst of packet traffic that caused the over-subscription goes away, the packets stored in the buffer 100 are drained from the buffer 100 and are distributed to egress ports. This allows for continuous operation of the data distribution device without loss of packets.
When, as shown in FIG. 1, the ports P0, P1 . . . P9 . . . PN of a data distribution device have each been operably connected and assigned to a statically-allocated buffer region 130, 140, 150, 160, each port has access to only a certain amount of the memory in the buffer 100. Hence, when the port P1 of the switch becomes over-subscribed, the port P1 may store excess packets in the first statically-allocated buffer region 140, up to the HWM 120. However, if packets attempting to use port P1 as an egress fill up the entire first statically-allocated buffer region 140, continued over-subscription of the port P1 results in dropping/discarding/loss of incoming packets, even though regions 130, 140, 150, 160, etc. are available. As one skilled in the art will appreciate, this is an undesirable condition.
FIG. 2 illustrates a second cell pool buffer 200 according to the related art. This second cell pool buffer 200 alleviates some of the problem of the first cell pool buffer 100 illustrated in FIG. 1.
The second cell pool buffer 200 contains a set of five representative ports P0, P1, P2, P3, P4 and, like the first cell pool buffer 100 illustrated in FIG. 1, has an LWM 210. In order to simplify comparisons between the FIG. 1 and FIG. 2, dashed vertical lines are included to show where the statically-allocated buffer regions 130, 140, 150, 160 illustrated in FIG. 1 would be positioned in the second cell pool buffer 200, had the second cell pool buffer 200 been divided similarly to the first cell pool buffer 100. It should be noted, however, that the vertical lines are provided only for the sake of comparison and that no statically-allocated buffer regions are included in the second cell pool buffer 200.
Unlike the first cell pool buffer 100, the second cell pool buffer 200 does not make use of an HWM for each of the ports operably connected thereto. Rather, when a port that is operably connected to the second cell pool buffer 200 needs to store a number of packets that would have exceeded the capacity of one of the statically-allocated buffer regions illustrated in FIG. 1, a port that is operably connected to the second buffer 200 illustrated in FIG. 2 is capable of storing packets in any buffer region that is available. In other words, if there is a region of the second cell pool buffer 200 above the LWM 210 that is not already storing a packet, any of the ports P0, P1, P2, P3, P4 operably connected to the second buffer 200 may store a packet in that region.
When the second cell pool buffer 200 is utilized as shown in FIG. 2, the port P3 does not store any packets in the regions above the LWM 210 and the port P2 uses only a small portion of what would have been its statically-allocated buffer region according to the first cell pool buffer 100. On the other hand, the port P0 slightly exceeds the capacity of what would have been its statically-allocated buffer region, and the port P4 greatly exceeds the capacity of what would have been its statically-allocated region. Therefore, in FIG. 2, all of the second buffer's 200 memory illustrated above the LWM 210 is used.
In FIG. 2, the ports P0 and P4 have each been oversubscribed enough that packets would have been dropped if the first cell pool buffer 100 illustrated in FIG. 1 had been used. Of course, in FIG. 1, unused memory would have been present in statically-allocated buffer regions allocated to the ports P1, P2, and P3. Therefore, inefficient memory usage would have resulted.
Fortunately, using the second cell pool buffer 200 as shown if FIG. 2, no packets are lost and efficient use is made of all available memory. However, under the second cell pool buffer 200 distribution shown in FIG. 2, if any of the ports attempted to store additional packets, this would not be possible. Rather, because maximum capacity of the second cell pool buffer 200 has already been attained, the additional packets would be dropped, regardless of which port was attempting to store them.
At least in view of the above, it should be apparent that one of the problems associated with allocation of memory cells/space in the second cell pool buffer 200 illustrated in FIG. 2 is that any one port can “use up” a large amount of the second cell pool buffer 200, thereby depriving other ports the use of any cell pool buffer regions above the LWM 210. This situation becomes particularly problematic when a single port, such as a port that only slowly “drains” packets from memory cells to egress ports, frequently deprives the other ports of access to regions of the buffer 200. In such situations, the second cell pool buffer 200 allows unfair, long-term monopolization of the buffer 200 by one port, to the detriment of the other ports connected to the data distribution device containing the buffer 200.
At least in view of the above, there is a need for methods of allocating memory in a memory buffer, wherein the methods do not suffer from the shortcomings of the related art. In addition, there is a need for system for storing datagrams, wherein the systems are capable of implementing such methods.